import java.util.*;
public class test {
    // leetcode 面试题08.06.汉诺塔问题
    class Solution {
        public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
            move(A.size(),A,B,C);
        }
        public void move(int size,List<Integer> n1,List<Integer> n2,List<Integer> n3){
            if(size == 1){
                n3.add(n1.remove(n1.size() - 1));
                return;
            }
            move(size - 1,n1,n3,n2);
            n3.add(n1.remove(n1.size() - 1));
            move(size - 1,n2,n1,n3);
        }
    }
    // leetcode 21.合并两个有序链表(递归法)
    // 递归法
    class Solution {
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            if (list1 == null) {
                return list2;
            }
            if (list2 == null) {
                return list1;
            }
            if (list1.val <= list2.val) {
                list1.next = mergeTwoLists(list1.next, list2);
                return list1;
            } else {
                list2.next = mergeTwoLists(list1, list2.next);
                return list2;
            }
        }
    }
    // leetcode 206.反转链表(递归法)
    // 递归法
    class Solution {
        public ListNode reverseList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            // 1 -> 2 -> 3 -> 4 -> 5
            // 反转链表 [反转链表].next = head;
            ListNode cur = reverseList(head.next);
            head.next.next = head;
            head.next = null;

            return cur;
        }
    }
    // leetcode Pow(x,n) (快速幂)
    class Solution {
        public double myPow(double x, int n) {
            return n > 0 ? pow(x,n) : 1.0 / pow(x,-n);
        }
        public double pow(double x,int n){
            if(n == 0){
                return 1;
            }
            double num = pow(x,n / 2);
            return n % 2 == 0 ? num * num : num * num * x;
        }
    }
}
